package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 676. 实现一个魔法字典
 * 剑指 Offer II 064. 神奇的字典
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/19 9:08
 */
public class MagicDictionary {


    public static void main(String[] args) {

        MagicDictionary test = new MagicDictionary();
        boolean search = true;

        // false, true, false, false
        test.buildDict(new String[]{"hello", "leetcode"});
        search = test.search("hello");
        System.out.print(search + "   ");
        search = test.search("hhllo");
        System.out.print(search + "   ");
        search = test.search("hell");
        System.out.print(search + "   ");
        search = test.search("leetcoded");
        System.out.print(search + "   ");
        System.out.println();

    }


    private Tree[] roots;

    public MagicDictionary() {
        roots = new Tree[26];
    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            addWord(s);
        }
    }

    public void addWord(String word) {
        char[] chars = word.toCharArray();
        find(roots, chars, 0);
    }

    private void find(Tree[] nodes, char[] chars, int index) {
        char aChar = chars[index];
        Tree node = nodes[aChar - 'a'];
        if (node == null) {
            node = new Tree();
            nodes[aChar - 'a'] = node;
        }
        node.have = true;
        if (index == chars.length - 1) {
            node.end = true;
            return;
        }
        find(node.nexts, chars, index + 1);
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        return f(roots, chars, 0, 1);
    }

    private boolean f(Tree[] nodes, char[] chars, int index, int flag) {
        char c = chars[index];
        for (int i = 0; i < 26; i++) {
            Tree node = nodes[i];
            if (node != null && node.have) {
                int item = flag;
                if (i != c - 'a') {
                    item--;
                }
                if (node.end && chars.length - 1 == index && item == 0) {
                    return true;
                }
                if (chars.length - 1 == index || item < 0) {
                    continue;
                }
                if (f(node.nexts, chars, index + 1, item)) {
                    return true;
                }
            }
        }
        return false;
    }

    private class Tree {
        private boolean have;
        private boolean end;
        private Tree[] nexts = new Tree[26];
    }

}
